Algorithm/Architecture Co-exploration (AAC) design methodology that can concurrently explore both algorithms and architectures based on intrinsic algorithmic complexity extraction and analysis becomes a design paradigm in the emerging electronic system level (ESL) design era. Intrinsic data transfer rate of algorithms is one of the important complexity metrics that can facilitate the exploration of the bandwidth for generic platforms for the ever more complex algorithms adopted in modern and future signal and information processing applications. Hence, quantifying data transfer rates needed by algorithms becomes necessary and essential for concurrently optimizing both algorithms and architectures.
Ravasi et al. have proposed to extract the computational complexity of algorithms by software instrumentation and estimation of the data-transfer and storage requirements based on the customizable virtual memory architecture (M. Ravasi and M. Mattavelli, “High-abstraction level complexity analysis and memory architecture simulations of multimedia algorithms,” IEEE Trans. on Circuits and Systems for Video Technology, pp. 673-684, Vol. 15, No. 5, May 2005.). This technique can effectively extract the platform-independent computational complexity. However, the data-transfer and storage requirements are rather dependent upon the customizable virtual memory architecture and, therefore, are not intrinsic to the algorithm itself.
The existing technique (e.g., M. Horowitz, A. Joch, F. Kossentini and A. Hallapuro, “H.264/AVC baseline profile decoder complexity analysis,” IEEE Trans. on Circuits and Systems for Video Technology, pp. 704-716, Vol. 13, No. 7, July 2003.) measures the complexity of algorithms by profiling them on various target platforms. The amounts of data transfer of algorithms are measured in terms of loading and storing operations in Horowitz et al. The major drawback of this prior art (Horowitz et al.) is that the measured algorithmic complexity on data transfer rate depends rather on the target processor-oriented platforms but not on the algorithms themselves. Therefore, the complexity measured is again not intrinsic to the algorithms and is biased by the target platforms.
Since the data transfer rates are significantly influenced by the data granularity of the dataflow representing the algorithms, data transfer rates measurements at multiple data granularities is essential and necessary to characterize the complexity of algorithms. However, the two aforementioned techniques do not support multigrain data transfer rate analysis. This is also a major drawback of the two techniques.
Keeping the drawbacks of the prior arts in mind, and employing experiments and research full-heartily and persistently, the applicant finally conceived a quantifying method for intrinsic data transfer rate of algorithms.